package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

import java.util.Arrays;

public class BinarySearchDemo {
    public int BaseSearch(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    @Test
    public void test01() {
        int[] arr = {-1, 0, 3, 5, 9, 12};
        System.out.println(BaseSearch(arr, 9));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        if (nums == null || nums.length == 0) {
            return ret;
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] != target) {
            return ret;
        }
        ret[0] = left;

        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;
    }

    @Test
    public void test02() {
        int[] arr = {5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(searchRange(arr, 8)));
    }

    public int mySqrt1(int x) {
        if (x == 1 || x == 0) {
            return x;
        }
        int left = 0, right = x / 2;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }

    // 牛顿迭代法
    public int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }
        long ret = x;
        while (ret > x / ret) {
            ret = (ret + x / ret) / 2;
        }
        return (int) ret;
    }

    @Test
    public void test03() {
        System.out.println(mySqrt1(8));
        System.out.println(mySqrt1(4));
        System.out.println(mySqrt1(2147395599));
        System.out.println(mySqrt1(2147395600));
        System.out.println(mySqrt2(8));
        System.out.println(mySqrt2(4));
        System.out.println(mySqrt2(2147395599));
        System.out.println(mySqrt2(2147395600));
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    @Test
    public void test04() {
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 5));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 7));
    }

    public int peakIndexInMountainArray1(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid - 1] < arr[mid] && arr[mid] < arr[mid + 1]) {
                left = mid;
            } else if (arr[mid - 1] > arr[mid] && arr[mid] > arr[mid + 1]) {
                right = mid;
            }

        }
        return -1;
    }

    public int peakIndexInMountainArray2(int[] arr) {
        int left = 0, right = arr.length - 2, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    @Test
    public void test05() {
        System.out.println(peakIndexInMountainArray1(new int[]{0, 1, 0}));
        System.out.println(peakIndexInMountainArray1(new int[]{0, 2, 1, 0}));
        System.out.println(peakIndexInMountainArray1(new int[]{0, 2, 7, 9, 10, 5, 2}));
        System.out.println(peakIndexInMountainArray1(new int[]{0, 2, 5, 7, 4, 3, 0}));
    }

    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (nums.length == 1 || nums[0] > nums[1]) {
            return 0;
        }
        if (nums.length == 2) {
            return nums[1] > nums[0] ? 1 : 0;
        }
        if (nums[n - 1] > nums[n - 2]) {
            return n - 1;
        }
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if (nums[mid - 1] < nums[mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    @Test
    public void test06() {
        System.out.println(findPeakElement(new int[]{1, 2, 3, 1}));
//        System.out.println(findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4}));
    }

    public int findMin(int[] nums) {
        int n = nums.length;
        if (n == 1 || nums[0] < nums[n - 1]) {
            return nums[0];
        }
        int left = 0, right = n - 1, mid;
        while (left < right) {
            mid = left + (right - left + 1) /2 ;
            if (nums[left] < nums[right] || nums[left] > nums[left++ + 1]) {
                return nums[left];
            }
            if (nums[left] > nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }

    @Test
    public void test07() {
        System.out.println(findMin(new int[]{3, 4, 5, 1, 2}));
        System.out.println(findMin(new int[]{4, 5, 6, 7, 0, 1, 2}));
        System.out.println(findMin(new int[]{11, 13, 15, 17}));
        System.out.println(findMin(new int[]{2, 1}));
        System.out.println(findMin(new int[]{3, 1, 2}   ));
    }

    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    @Test
    public void test08() {
        System.out.println(missingNumber(new int[]{
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15
        }));
    }
}
